// 先将我们的数组变成一个最大堆
// 对最大堆进行排序(将最前面的数值和最后一项目交换位置)

import { cbtPrint, measureSort, swap, testSort } from "hy-algokit";

export default function heapSort(arr:number[]):number[]{

    // 1.获取数组的长度
    const n = arr.length;
    // 2.对arr进行原地建堆
    // 2.1从第一个非叶子节点进行下滤操作
    const start = Math.floor((n/2)-1);
    for (let i = start; i >= 0 ; i--){
        heapifyDown(arr,n,i)
    }

    // 对最大堆进行排序的操作
    for(let i = n-1;i > 0; i--){
        // 将第一个元素（最大的元素，和当前数组的最后一个元素进行位置的交换）
        swap(arr,0,i);
        // 从第一个元素进行下滤
        heapifyDown(arr,i,0)
    }
    // console.log(arr)
    // cbtPrint(arr)

    
    return arr;
}

function heapifyDown(arr:number[],n:number,index:number){
    while(2 * index +1 < n){
        // 1.获取左子节点和右子节点的索引
        const leftChildIndex = 2 * index +1 ;
        const rightChildIndex = 2 * index + 2;
        // 2.找出左右子节点较大的值
        let largerIndex = leftChildIndex;
        if(rightChildIndex < n && arr[rightChildIndex] > arr[leftChildIndex]){
            largerIndex = rightChildIndex;
        }
        // 3. 如果index位置的值比左右子节点的值中较大的值还要大，直接break
        if(arr[index] >= arr[largerIndex]){
            break;
        }
        // 4. 和更大位置的值进行交换
        swap(arr,index,largerIndex);
        index = largerIndex
    }
}


// heapSort([
//     17, 144, 127, 140,
//     23,  98, 102, 104,
//     15, 170
//   ])
testSort(heapSort)
measureSort(heapSort)